package subject.dp;

public class maxProduct {
    public int maxProduct1(int[] nums) {
        // 初始化：以第一个元素结尾的子数组，最大值、最小值都是它本身
        long maxF = nums[0]; // 当前最大乘积（以当前位置结尾）
        long minF = nums[0]; // 当前最小乘积（以当前位置结尾）
        int ans = nums[0];   // 全局最大乘积

        // 从第二个元素开始遍历
        for (int i = 1; i < nums.length; ++i) {
            // 保存上一步的计算结果（因为下一步会覆盖）
            long prevMax = maxF;
            long prevMin = minF;

            /* 核心动态规划方程：
               当前最大乘积可能来自三种情况：
               1. 前一个最大乘积 * 当前数（正数增益）
               2. 当前数自身（断掉前面的子数组）
               3. 前一个最小乘积 * 当前数（负数负负得正）*/
            maxF = Math.max(prevMax * nums[i],
                    Math.max(nums[i], prevMin * nums[i]));

            /* 当前最小乘积可能来自三种情况：
               1. 前一个最小乘积 * 当前数（负数继续减小）
               2. 当前数自身
               3. 前一个最大乘积 * 当前数（正数乘负数变小）*/
            minF = Math.min(prevMin * nums[i],
                    Math.min(nums[i], prevMax * nums[i]));

            // 更新全局最大乘积
            ans = Math.max(ans, (int)maxF);
        }
        return ans;
    }

}
